package com.guoxin.tree.binarytree;

/**
 * 树的骨架类
 *
 * @author guoxin
 * @date 2019/7/27
 */
public class Tree {

    public Tree() {
        this.root = null;
    }

    /** 树中包含的节点 */
    private Node root;

    /** 查询 */
    public Node find(int key) {
        // 从根节点开始
        Node current = root;
        while (current.getData() != key) {
            //如果当前节点值小于查询的值，向右
            if (key >= current.getData()) {
                current = current.getRightNode();
            }
            //如果当前节点值大于查询的值，向左
            if (key < current.getData()) {
                current = current.getLeftNode();
            }

            if (current == null) {
                return null;
            }
        }
        return current;
    }

    /** 添加 */
    public void add(int key, float fData) {
        if (root == null) {
            root = new Node(key, fData);
            return;
        }
        //当前节点，从根节点开始
        Node current = root;
        //用于存储最后一个不为null的父节点
        Node parent;
        boolean flag = true;
        while (flag) {
            parent = current;
            if (key >= current.getData()) {
                current = current.getRightNode();
                if (current == null) {
                    parent.setRightNode(new Node(key, fData));
                    flag = false;
                }
            } else {
                current = current.getLeftNode();
                if (current == null) {
                    parent.setLeftNode(new Node(key, fData));
                    flag = false;
                }
            }
        }
    }

    /**
     * 中序遍历
     * 中序遍历二叉搜索树会使所有的节点按关键字值升序被访问到；
     * 遍历树最简单的方法是使用递归，用递归的方法遍历整颗二叉树需要时用一个节点作为参数，初始化时这个节点时根节点。
     * 1.调用自身来遍历节点的左子树
     * 2.访问这个节点
     * 3.调用自身来遍历节点的右子树
     */
    public void inOrder(Node localRoot) {
        if (localRoot != null) {
            inOrder(localRoot.getLeftNode());
            System.out.println(localRoot.getData() + " ");
            inOrder(localRoot.getRightNode());
        }
    }

    /**
     * 先序遍历
     */
    public void preOrder(Node localRoot) {
        if (localRoot != null) {
            System.out.println(localRoot.getData() + " ");
            preOrder(localRoot.getLeftNode());
            preOrder(localRoot.getRightNode());
        }
    }

    /**
     * 后序遍历
     */
    public void postOrder(Node localRoot) {
        if (localRoot != null) {
            postOrder(localRoot.getLeftNode());
            postOrder(localRoot.getRightNode());
            System.out.println(localRoot.getData() + " ");
        }
    }

    /** 查找最小的节点 */
    public Node findMin() {
        Node current, last = null;
        current = root;
        while (current != null) {
            last = current;
            current = current.getLeftNode();
        }
        return last;
    }

    /** 查找最大的节点 */
    public Node findMax() {
        Node current, last = null;
        current = root;
        while (current != null) {
            last = current;
            current = current.getRightNode();
        }
        return last;
    }

    /**
     * 删除
     * 删除节点考虑三种情况：
     * 1.该节点是叶子节点
     * 2.该节点有一个子节点
     * 3.该节点有两个子节点
     */
    public boolean delete(int key) {
        Node current, parent;
        current = root;
        parent = root;
        boolean isLeftNode = true;
        //查找节点的位置
        while (current.getData() != key) {
            parent = current;
            if (key < current.getData()) {
                current = current.getLeftNode();
                isLeftNode = true;
            } else {
                current = current.getRightNode();
                isLeftNode = false;
            }
            //没有找到
            if (current == null) {
                return false;
            }
        }
        //删除没有子节点的节点
        if (current.getLeftNode() == null && current.getRightNode() == null) {
            if (current == root) {
                root = null;
            } else if (isLeftNode) {
                parent.setLeftNode(null);
            } else {
                parent.setRightNode(null);
            }
            //删除有一个子节点的位置，有四种不同的情况：
            // 要删除的节点可能是左子节点或右子节点，并且每种情况中要删除节点也可能是自己父节点的左子节点或右子节点
        } else if (current.getRightNode() == null) {
            if (current == root) {
                root = current.getLeftNode();
            } else if (isLeftNode) {
                parent.setLeftNode(current.getLeftNode());
            } else {
                parent.setRightNode(current.getLeftNode());
            }
        } else if (current.getLeftNode() == null) {
            if (current == root) {
                root = current.getRightNode();
            } else if (isLeftNode) {
                parent.setLeftNode(current.getRightNode());
            } else {
                parent.setRightNode(current.getRightNode());
            }
            //删除有两个子节点的节点，用它的中序后序来代替该节点
        } else {
            Node successor = getSuccessor(current);
            if (successor == root) {
                root = successor;
            } else if (isLeftNode) {
                parent.setLeftNode(successor);
            } else {
                parent.setRightNode(successor);
            }
            successor.setLeftNode(current.getLeftNode());
        }
        return true;
    }

    /**
     * 找到后继节点
     * 首先程序找到初始节点的右子节点，它的关键值一定比初始节点大，然后转到初始节点的右子节点的左子节点那里，然后到这个左子节点的左子节点，
     * 以此类推顺着左子节点的路径往下找。这个路径上的最后一个左子节点就是初始节点的后继节点。
     * 以上是找到初始节点的右子树的最小节点
     */
    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.getRightNode();
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.getLeftNode();
        }
        if (successor != delNode.getRightNode()) {
            successorParent.setLeftNode(successor.getRightNode());
            successor.setRightNode(delNode.getRightNode());
        }
        return successor;
    }
}
